package offer.day15;

public class No22findKthToTail {
    /*
     * 面试题22：链表中倒数第k个节点
     * 题目:输入一个单向链表，输出该链表中倒数第k个节点。
     * 为了符合大多数人的习惯，本体从1开始计数，即链表的尾节点是倒数第一个节点
     * 例如：一个链表有6个节点，从头节点开始，他们的值依次是1、2、3、4、5、6.
     * 这个链表的倒数第3个节点是值为4的节点。
     * 链表定义：
     * struct ListNode{
     * 	int m_nValue;
     *  LinkNode m_pnext;
     * }
     *
     * 思路：
     * 方法一：遍历两边链表  ：第一遍统计链表的个数n，第二遍根据n值和k值，得到要从头节点向后走到第n-k+个节点。但是此方法要遍历两边链表。
     * 方法二：遍历一遍链表：设置两个指针，都设置在头节点，第一个指针先走k-1步，第二个指针不动；
     * 从第k步开始，第二个指针向后移动，第一个指针也向后移动，直到第一个指针走到链表的尾部。
     * 因为 开始第一个指针走了k-1步 到达 第k个节点  然后还剩余n-k个节点，然后两个指针一起走，直到第一个指针到达尾部，那就走n-k+1步，
     * 完成这长度为n【k-1步+n-k+1步 == n步】的链表的依次遍历
     *
     * */

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        ListNode six = new ListNode(6);

        head.next = second;
        second.next = three;
        three.next = four;
        four.next = five;
        five.next = six;
        six.next = null;

        showNode(head);
        int k=4;
        System.out.println(findTailNode(head,k));
    }

    public static ListNode findTailNode(ListNode head,int k){
        if(head==null) return null;
        ListNode t1=head;
        ListNode t2=head;
        for(int i=0;i<k-1;i++){
            t1=t1.next;
        }
        while(t1.next!=null){
            t1=t1.next;
            t2=t2.next;
        }
        return t2;

    }

    public static void showNode(ListNode head){
        ListNode tmp=head;
        while(tmp!=null){
            System.out.println(tmp);
            tmp=tmp.next;
        }
        System.out.println();
    }
}
